{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 定点数示例\n",
    "\n",
    "参考：[定点表示：Q 格式和加法示例](https://www.allaboutcircuits.com/technical-articles/fixed-point-representation-the-q-format-and-addition-examples/) & [A Fixed-Point Introduction by Example](https://www.dsprelated.com/showarticle/139.php)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Q（数字）格式是一种定点方法，用于编码小数和整数，以便由计算机的 CPU 或数字信号处理器（[DSP](https://www.techtarget.com/whatis/definition/digital-signal-processing-DSP)）进行处理。Q 格式用于通过标准整数硬件算术逻辑单元 （ALU） 实现有理数处理。当 CPU 缺少浮点单元 （FPU） 时，经常使用 Q 格式。该格式还可用于在低成本 DSP 上处理分数（fractions），从而降低硬件成本。\n",
    "\n",
    "为了在较低成本或较旧的硬件上处理分数，Q 用于表示二进制小数点来表示分数。Q 格式以常规二进制有符号整数的形式存储和处理。Q 格式指定了用于表示整数部分的位数以及用于表示小数部分的位数。例如，如果要指出某个算法使用 1 位来指定整数部分，并使用 15 个位来指定小数部分，则可以使用 Q1.15 格式。如果 Q 格式中没有小数，例如 Q55，则表示所有位都用于表示小数值。\n",
    "\n",
    "分数在 Q 格式下处理的示例：\n",
    "\n",
    "实数 5.375，表示为 $a = 0×2^3 + 1×2^2 + 0×2^1 + 1×2^0 + 0×2^{-1} + 1×2^{-2} + 1×2^{-3} + 0×2^{-4} = 5.375$(Q4.4)。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "分数的有限字表示被称为定点数（fixed-point）。定点数是对二进制补码数字的解释，通常用于有符号表示，但不限于符号表示。它扩展了有限字长的范围，从有限的整数集合到有限的有理实数集合[1](http://www.digitalsignallabs.com/fp.pdf)。数的定点数表示由整数和小数部分组成。位长度定义为：\n",
    "\n",
    "$$\n",
    "X_{Nbits} = 1 + X_{Integer Nbits} + X_{Fraction Nbits}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`IWL` 表示整数字长，`FWL` 表示小数字长，则总字长 `WL`，可以表示为：$WL = 1 + IWL + FWL$。使用这种表示法，数字的范围是 $\\left[ -2^{IWL}, 2^{IWL} \\right)$，步长（分辨率（resolution））为 $2^{-FWL}$ {cite:p}`STFP`。定点数由其格式 wl、iwl、fwl 或其属性范围(range)、分辨率(resolution)和偏置(bias)定义。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如上所述，定点数由其范围和分辨率定义，而不是由位数定义。在设计定点系统时，使用范围和分辨率要求并算法地解决实现设计时的位数是符合逻辑的。换句话说，在设计和指定时从范围和分辨率开始，并在实现时转移到所需的位数。通常，缩写表示格式。在讨论定点处理器时，Q 格式是常见的。在这里，将使用显式表示法 `W=(wl, iwl, fwl)`。（注：这里不会使用 Q 格式，因为它不够灵活，并且可能会与旧的定点处理器文档中使用的符号混淆[3](http://www.ee.ic.ac.uk/pcheung/teaching/ee3_Study_Project/lecture%205(4).pdf)。）这个符号定义了整数位数、小数位数和总位数。例如，`W=(4,0,3)` 是 4 位的数，其中包含 3 个小数位和 1 个符号位（符号位是隐含的）。本篇博文中的所有定点数都将采用 2 的补码表示法（符号位始终存在）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 为什么使用定点表示法？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "为什么不简单地将所有值规范化到整数范围并处理整数。根据您的观点，这可能显而易见或不明显。我发现许多设计师倾向于将所有值规范化为整数，但这会产生非常难以阅读的代码和文档。定点通常用于方便（类似于 $\\exp{j\\omega}$ 的使用）。例如，如果查看源代码并看到：\n",
    "```c++\n",
    "c0 = fixbv(0.0032, min=-1, max=1, res=2**-15)\n",
    "c1 = fixbv(-0.012, min=-1, max=1, res=2**-15)\n",
    "```\n",
    "\n",
    "可以很容易地将这归结为滤波器的系数，但是如果只看到整数使用：\n",
    "```c++\n",
    "c0 = intbv(0x0069, min=-2**15, max=2**15)\n",
    "c1 = intbv(-0x0189, min=-2**15, max=2**15)\n",
    "```\n",
    "\n",
    "需要额外的信息（文档）。仅使用整数很难理解这些值所代表的含义。除了表示上的好处之外，处理舍入和溢出的工具在固定点类型中也很常见。\n",
    "\n",
    "现在给出了定点二进制的基本定义，并给出了一些使用定点的原因。让我们看一下一些转换为定点类型的小数值。表 1 是定点表示法的示例。\n",
    "![](images/fixed-point-table.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "前两个例子说明了如何使用定点命名法表示小数值。一般来说，如果将整数部分和小数部分视为单独的位向量（即不共享位索引），则二进制字的值如下：\n",
    "\n",
    "$$\n",
    "{\\displaystyle\\sum_{k=0}^{IWL-1} b_{I}[k]2^k} + {\\displaystyle\\sum_{k=0}^{FWL-1}b_{F}[k]2^{-(k+1)}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在上述等式中，它假设位大小随着位索引的增加而增加。如果将小数字可视化，则相对于上面的描述，它将被翻转(flipped)。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "以下是定点乘法和加法的示例。定点减法可以以类似于 2 的补码减法（负数相加）的方式计算。区别在于需要进行“点”记录，这与加法相同。对于加法和减法，操作之前需要对齐“点”（记录(bookkeeping)）。通常在设计时计算“点”记录，而不是运行时（通常是因为存在块定点的概念，但这超出了本文的范围）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 定点乘法简介\n",
    "\n",
    "定点乘法与 2 的补码乘法相同，但需要在乘法后确定“点”的位置以解释正确的结果。“点”位置的确定是设计任务。实际实现不知道（或不关心）“点”的位置在哪里。这是正确的，因为定点乘法与 2 的补码乘法完全相同，不需要特殊硬件。\n",
    "\n",
    "以下是一个示例，说明了 $6.5625 (W=(8,3,4)) * 4.25 (W=(8,5,2))$："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "0110.1001  == 6.5625\n",
    "000100.01  == 4.25\n",
    "          01101001  \n",
    "        x 00010001  \n",
    "      ------------\n",
    "          01101001\n",
    "         00000000 \n",
    "        00000000  \n",
    "       00000000  \n",
    "      01101001    \n",
    "     00000000      \n",
    "    00000000\n",
    "   00000000 \n",
    " --------------------\n",
    "  x000011011111001   ==  0000011011.111001  ==  27.890625\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "乘积（结果）所需的位数是被乘数的 `WL` + 乘数的 `ML`：$WL_{multiplicand} + WL_{multiplier}$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "乘法（和加法）结果的大小通常被调整，并且位的数量减少。在定点中，这具有直观的意义，因为较小的小数位被丢弃，并且基于被丢弃的位对值进行舍入。通常包括额外的硬件来完成舍入任务，并将位数减少到合理的数据路径总线宽度(data-path bus width)。\n",
    "\n",
    "## 符号扩展\n",
    "\n",
    "当将两个带符号的数字相加时，被加数和加数可能具有不同的长度。在这种情况下，我们必须扩展较短数字的符号位，否则结果可能不正确。\n",
    "\n",
    "例如，将 $1011_{2}$ 的符号扩展两位，我们得到 $111011_{2}$。这种符号位复制是如何证明其合理性的呢？我们知道在正数左侧放置零不会改变其值。要理解为什么符号扩展不会改变负数的值，我们应该记住，在二进制补码表示中，负数是根据[互补常量](https://www.allaboutcircuits.com/technical-articles/twos-complement-representation-theory-and-examples/)定义的。使用 $k$ 位数字，二进制补码表示的互补常量(complementation constant)为 $M=2^{k}$。\n",
    "\n",
    "举个例子，当使用四位数字时，互补常量将是 $M = 2^4$，四位数字 $b$ 的相反数将由 $M - b$ 表示。让我们看看如何使用六个位来表示这个带符号的四位数字。\n",
    "\n",
    "为了使用六个位来表示 $b$ 的相反数，我们应该使用 $M' = 2^6$，并将 $-b$ 表示为 $M' - b$。因此，六位表示和四位表示之间的差异是 $(M'-b)-(M-b)=M'-M=2^{6}-2^{4}=0110000_{2}$。这表明，为了使用六位表示四位负数，我们只需要将 $0110000_{2}$ 添加到该四位表示中，或者等效地，我们可以扩展符号位两位。\n",
    "\n",
    "简单来说，通过复制数字的符号位，只是改变了互补常量，而该数字的值并没有改变。您也可以通过计算此示例的四位和六位表示的十进制等效值来验证此陈述。$1011_{2}$ 的十进制等效值为其二进制补码的相反数，即 -$-(0101_{2})=-5_{10}$。同样，$111011_{2}$ 的十进制值为 $-(0101_{2})=-5_{10}$。如您所见，等效的十进制值不会随符号扩展而改变。\n",
    "\n",
    "## 定点加法\n",
    "\n",
    "加法稍微复杂一些，因为执行加法之前需要对齐“点”。使用乘法问题中的相同数字：\n",
    "\n",
    "```\n",
    "0110.1001  == 6.5625\n",
    "000100.01  == 4.25\n",
    "            0110.1001  \n",
    "        + 000100.01  \n",
    "        -------------\n",
    "          001010.1101  ==  10.8125\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "当将两个数字相加（或相减）时，结果需要额外的一位。当将超过两个相同 `WL` 宽度的数字相加时，结果所需的位数为 $WL + log_2(N)$，其中 `N` 是正在求和的元素数量。\n",
    "\n",
    "假设使用浮点算法测试的以下数据的运算：$a=9.216957436091198_{10}$，现在我们对算法在浮点表示中的表现感到满意，决定将其实现在低成本的 16 位定点处理器上。那么在这种处理器上，什么合适的 Q 格式来表示 $a$ 呢？\n",
    "\n",
    "由于 $a$ 的整数部分在十进制值 $8$ 和 $16$ 之间，我们需要至少 4 位来表示数字的整数部分。假设处理的是带符号的数字，我们可以将二进制点向左移动 5 位，并使用剩余的位数表示小数部分。因此，我们可以使用 Q5.11 格式。\n",
    "\n",
    "在这种格式中，实现的二进制表示将使用 $2^{-11}$ 的缩放因子进行解释。换句话说，没有隐含二进制“点”的 $a$ 的 Q5.11 表示等于 $a$ 被乘以 $2^{11}$。因此，为了在 Q5.11 格式中表示 $a$，我们将其乘以 $2^{11}$，四舍五入到最接近的整数，并将四舍五入的结果转换为二进制形式。我们得到\n",
    "\n",
    "$$\n",
    "a \\times 2^{11}=18876.3288 \\approx 18876 = 100\\;1001\\; 1011\\; 1100_{(2)}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "由于 $a$ 是正数，我们只需要考虑零符号位。因此，该数字的 Q5.11 格式将是 $01001.00110111100$。\n",
    "\n",
    "对于负数，首先需要找到其绝对值的 Q 格式，然后将其转换为二进制补码表示以考虑负号。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假设 $a=10.01_{2}$ 是 Q2.2 格式的数字。由于符号位为 1，因此等效的十进制值将是 $a$ 的二进制补码 $01.11_{2}$。因此，我们有 $a=-1.75_{10}$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "为了在 Q 格式中相加两个数字，我们应该首先对齐两个数字的二进制小数点，并对整数部分较短的数字进行符号扩展。让我们看一个例子："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "计算 $a + b$，其中 $a = -1.25$（注意，$-1.01_{2}$ 在二进制补码表示中变为 $10.11_{2}$），$b = +3.25$（在二进制补码表示中变为 $011.010_{2}$）。如您所见，$a$ 和 $b$ 分别是 Q2.2 和 Q3.3 格式的两个带符号数字。\n",
    "\n",
    "我们应该首先对齐两个数字的二进制小数点，并对整数部分较短的数字进行符号扩展，然后执行加法运算。我们得到"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{math}\n",
    "\\begin{split} \\; \\; 1 \\; 1 \\; 0 \\; &. \\; 1 \\; 1 \\; \\; \\; &-1.25 \\\\  \n",
    "+ \\; \\; 0 \\; 1 \\; 1 \\; &. \\; 0 \\; 1 \\; 0 \\; \\; \\; &+3.25 \\\\  \n",
    "\\hline \\\\ \n",
    "\\; 1 \\; 0 \\; 1 \\; 0 \\; &. \\; 0 \\; 0 \\; 0 \\; \\; \\; \\; &+2 \n",
    "\\end{split}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "除了隐含的缩放因子之外，上述加法与在二进制补码表示中相加两个数字完全相同。由于二进制补码表示基于模数 M 算术，因此显然我们应该丢弃结果中高于符号位的位。因此，$a+b=010.000_2=+2_{10}$ 这与上面显示的十进制结果一致。请注意，如果没有符号扩展，结果将不正确，因为在这种情况下，我们实际上有 $010.11_2=+2.75_{10}$ 和 $10.11_2=-1.25_{10}$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在使用定点表示进行算术运算时，我们必须注意给定 Q 格式可以表示的值的范围。作为一个例子，假设我们将 $Qn_a.m_a$ 格式的 $a$ 与 $Qn_b.m_b$ 格式的 $b$ 相加。类似于上述例子，我们可以使用较短的整数部分对数字进行符号扩展，并将结果表示为 $Qn_c.m_c$ 格式，其中 $n_c=\\max\\{n_a, n_b\\}$ 且 $m_c=\\max\\{m_a, m_b\\}$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "然而，我们应该注意到溢出的可能性，因为将两个 N 位数字相加可能导致（N+1）位的结果。使用上述结果的 Qnc.mc 格式，我们必须确保没有发生溢出。以下示例进一步阐明了这一点。\n",
    "\n",
    "$a=10.11_2$，$b=100.001_2$，$a+b$ 计算：我们应该首先对齐两个数字的二进制小数点，使用较短整数部分进行符号扩展，然后执行加法运算。我们得到\n",
    "\n",
    "```{math}\n",
    "\\begin{split} \\; \\; 1 \\; 1 \\; 0 \\; &. \\; 1 \\; 1 \\; \\; \\; &-1.25 \\\\ \n",
    "+ \\; \\; 1 \\; 0 \\; 0 \\; &. \\; 0 \\; 0 \\; 1 \\; \\; \\; &-3.875 \\\\ \n",
    "\\hline \\\\ \n",
    "\\; 1 \\; 0 \\; 1 \\; 0 \\; &. \\; 1 \\; 1 \\; 1 \\; \\; \\; \\; &-5.125 \n",
    "\\end{split}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果我们丢弃整数部分的第四位，我们得到 $010.111_2=2.875_{10}$。当我们将两个负数相加时，结果为正数，因此发生了溢出。这是由于在Q3.3格式中可以表示的最小数字是 $100.000_2=-4_{10}$，并且相加的结果小于 $-4_{10}$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "为了规避加法中的溢出，我们可以缩放输入或使用可以处理 Q4.3 格式数字的加法器。对于后者，我们必须对数字进行符号扩展，以在整数部分中有四个位。请注意，由于将两个 N 位数字相加可能导致（N+1）位的结果，因此 Q4.3 输出格式将在将两个 Q3.3 数字相加时避免溢出。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "计算 $a + b$，其中 $a = 10.11_2$ 和 $b = 100.001_2$ 分别是 Q2.2 和 Q3.3 格式的两个带符号数字。假设加法器可以处理 Q4.3 格式的数字。我们应该首先对齐两个数字的二进制小数点。由于 $a$ 和 $b$ 的整数部分都小于 4 位，因此我们应该将它们符号扩展到 Q4.3 格式，然后执行加法运算。我们得到\n",
    "\n",
    "```{math}\n",
    "\\begin{split} \\; \\; 1 \\; 1 \\; 1 \\; 0 \\; &. \\; 1 \\; 1 \\; \\; \\; &-1.25 \\\\ \n",
    "+ \\; \\; 1 \\; 1 \\; 0 \\; 0 \\; &. \\; 0 \\; 0 \\; 1 \\; \\; \\; &-3.875 \\\\ \n",
    "\\hline \\\\ \n",
    "\\; 1 \\; 1 \\; 0 \\; 1 \\; 0 \\; &. \\; 1 \\; 1 \\; 1 \\; \\; \\; \\; &-5.125 \n",
    "\\end{split}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "丢弃符号位以上的位，我们得到 $a+b=1010.111_2=-5.125_{10}$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 避免溢出的防护位\n",
    "\n",
    "许多数字信号处理器选择累加器的输出寄存器比其输入寄存器大几个比特。这些额外的比特被称为防护位（Guard Bits）。防护位允许程序员在不缩放累加器输入的情况下累积多个值，从而避免溢出。你可以轻松验证具有 $n$ 防护位的累加器允许我们累积 $2^n$ 个值而不会溢出。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "虽然我们可以使用更大的加法器来防止溢出，但我们不能无限地允许字长增长。因此，在我们的计算中，我们必须在某个地方截断或舍入加法结果到较短的字长。这通常意味着我们必须将更多的比特分配给加法结果的整数部分，以便我们可以表示更大的值。换句话说，我们必须改变二进制小数点的位置。"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
